// Copyright 2023 Ant Group Co., Ltd.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "psi/algorithm/rr22/okvs/simple_index.h"

#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>

#include "boost/math/special_functions/binomial.hpp"
#include "boost/multiprecision/cpp_bin_float.hpp"
#include "spdlog/spdlog.h"
#include "yacl/base/exception.h"

namespace psi::rr22::okvs {

namespace {
// template<unsigned int N = 16>
double GetBinOverflowProb(uint64_t num_bins, uint64_t num_balls,
                          uint64_t get_bin_size, double epsilon = 0.0001) {
  if (num_balls <= get_bin_size) return std::numeric_limits<double>::max();

  YACL_ENFORCE(num_balls <= std::numeric_limits<int32_t>::max(),
               "boost::math::binomial_coefficient(...) only supports   {} bit "
               "inputs which was exceeded.",
               std::to_string(sizeof(unsigned) * 8));

  // std::cout << numBalls << " " << num_bins << " " << binSize << std::endl;
  typedef boost::multiprecision::number<
      boost::multiprecision::backends::cpp_bin_float<16>>
      T;
  T sum = 0.0;
  T sec = 0.0;  // minSec + 1;
  T diff = 1;
  uint64_t i = get_bin_size + 1;

  while (diff > T(epsilon) && num_balls >= i /*&& sec > minSec*/) {
    sum +=
        num_bins *
        boost::math::binomial_coefficient<T>(int32_t(num_balls), int32_t(i)) *
        boost::multiprecision::pow(T(1.0) / num_bins, i) *
        boost::multiprecision::pow(1 - T(1.0) / num_bins, num_balls - i);

    T sec2 = boost::multiprecision::log2(sum);
    diff = boost::multiprecision::abs(sec - sec2);

    sec = sec2;

    i++;
  }

  return std::max<double>(0, static_cast<double>(-sec));
}

// log2(bin size) of mapping n balls to m bins, for 40 bit sec.
// row i has n=2^i bins, column j has m=2^j balls.
std::vector<std::vector<double>> logbin_sizes_40bit{{
    // log #bins        , log #balls
    //                    0, 1, 2, 3, 4, 5, 6,...
    /*0*/ {{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15,
            16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}},
    /*1*/ {{0,           1,           2,           3,           4,
            5,           5.857980995, 6.686500527, 7.523561956, 8.392317423,
            9.290018847, 10.21067134, 11.15228484, 12.10950422, 13.07831762,
            14.05579081, 15.03969019, 16.02818667, 17.01999243, 18.01416217,
            19.01002812, 20.00709846, 21.00502277, 22.00355291, 23.00251306,
            24.00177721, 25.00125665, 26.00088843, 27.00062802, 28.00044386,
            29.00031363}},
    /*2*/ {{0,           1,           2,           3,           4,
            4.754887502, 5.459431619, 6.129283017, 6.87036472,  7.665335917,
            8.491853096, 9.361943774, 10.2632692,  11.18982456, 12.13602985,
            13.09737377, 14.06936585, 15.04929552, 16.03499235, 17.02481502,
            18.01757508, 19.01244722, 20.00880883, 21.00623293, 22.00440908,
            23.00311846, 24.00220528, 25.00155925, 26.00110233, 27.00077917,
            28.00055063}},
    /*3*/ {{0,           1,           2,           3,           3.906890596,
            4.459431619, 5,           5.614709844, 6.247927513, 6.965784285,
            7.727920455, 8.539158811, 9.394462695, 10.28771238, 11.20762447,
            12.14879432, 13.10639936, 14.07581338, 15.05392588, 16.03827601,
            17.02713927, 18.01923236, 19.0136171,  20.00963729, 21.00681914,
            22.00482395, 23.00341171, 24.00241262, 25.00170588, 26.00120598,
            27.00085241}},
    /*4*/ {{0,           1,           2,           3,           3.700439718,
            4.087462841, 4.584962501, 5.129283017, 5.672425342, 6.321928095,
            7.011227255, 7.761551232, 8.566054038, 9.413627929, 10.30149619,
            11.21735191, 12.15608308, 13.11146174, 14.07948478, 15.05651071,
            16.04011845, 17.0284457,  18.02015526, 19.01427116, 20.0101019,
            21.00714706, 22.00505602, 23.0035759,  24.00252877, 25.00178798,
            26.00126401}},
    /*5*/ {{0,           1,           2,           3,           3.459431619,
            3.807354922, 4.247927513, 4.700439718, 5.169925001, 5.727920455,
            6.357552005, 7.033423002, 7.781359714, 8.581200582, 9.426264755,
            10.30947635, 11.22339841, 12.16050175, 13.11471839, 14.08173308,
            15.06149777, 16.04127413, 17.02926566, 18.02074126, 19.01468524,
            20.01039425, 21.00735446, 22.00520271, 23.00367969, 24.00260216,
            25.0018399}},
    /*6*/ {{0,           1,           2,           2.807354922, 3.169925001,
            3.584962501, 3.906890596, 4.321928095, 4.700439718, 5.209453366,
            5.754887502, 6.375039431, 7.055282436, 7.794415866, 8.592457037,
            9.434628228, 10.31514956, 11.22821744, 12.16364968, 13.11699368,
            14.08339622, 15.05930221, 16.04210821, 17.02985876, 18.0211535,
            19.01497939, 20.01060323, 21.00750229, 22.00530724, 23.00375379,
            24.00265452}},
    /*7*/ {{0,           1,           2,           2.807354922, 3,
            3.321928095, 3.584962501, 4,           4.321928095, 4.754887502,
            5.247927513, 5.781359714, 6.392317423, 7.06608919,  7.807354922,
            8.599912842, 9.440869168, 10.32080055, 11.23122118, 12.16616308,
            13.11877889, 14.08472536, 15.06023151, 16.04277086, 17.03032228,
            18.02148428, 19.0152163,  20.01076984, 21.00762,    22.00539086,
            23.0038128}},
    /*8*/ {{0,           1,           2,           2.584962501, 2.807354922,
            3.169925001, 3.321928095, 3.700439718, 4,           4.392317423,
            4.807354922, 5.247927513, 5.807354922, 6.409390936, 7.076815597,
            7.813781191, 8.607330314, 9.445014846, 10.32418055, 11.23421868,
            12.16835873, 13.1203999,  14.08580438, 15.0610336,  16.04332639,
            17.03073179, 18.02177162, 19.01541777, 20.01091459, 21.00772264,
            22.00546316}},
    /*9*/ {{0,           1,           2,           2.321928095, 2.584962501,
            3,           3.169925001, 3.459431619, 3.700439718, 4,
            4.392317423, 4.807354922, 5.285402219, 5.807354922, 6.426264755,
            7.087462841, 7.826548487, 8.614709844, 9.451211112, 10.32755264,
            11.23720996, 12.17023805, 13.12185725, 14.08679969, 15.06175089,
            16.04386035, 17.03109809, 18.02203723, 19.01560561, 20.01104704,
            21.00781707}},
    /*10*/ {{0,           1,           2,           2.321928095, 2.584962501,
             2.807354922, 3,           3.169925001, 3.459431619, 3.700439718,
             4.087462841, 4.392317423, 4.807354922, 5.285402219, 5.832890014,
             6.426264755, 7.098032083, 7.832890014, 8.618385502, 9.45532722,
             10.33203655, 11.23959853, 12.17211493, 13.12315143, 14.0877943,
             15.06246782, 16.04435143, 17.03145353, 18.02229195, 19.01578526,
             20.01117265}},
    /*11*/ {{0,           1,           2,           2.321928095, 2.321928095,
             2.584962501, 2.807354922, 3,           3.169925001, 3.459431619,
             3.700439718, 4.087462841, 4.459431619, 4.857980995, 5.321928095,
             5.832890014, 6.442943496, 7.108524457, 7.839203788, 8.625708843,
             9.459431619, 10.33539035, 11.24198315, 12.17398937, 13.12444446,
             14.08878824, 15.06314225, 16.04484233, 17.03179811, 18.02253579,
             19.01595672}},
    /*12*/ {{0,           1,           2,           2,           2.321928095,
             2.321928095, 2.584962501, 2.807354922, 3,           3.169925001,
             3.459431619, 3.807354922, 4.087462841, 4.459431619, 4.857980995,
             5.321928095, 5.857980995, 6.459431619, 7.118941073, 7.845490051,
             8.62935662,  9.463524373, 10.33873638, 11.24436384, 12.17586138,
             13.12573633, 14.08969874, 15.06381637, 16.04531174, 17.03213185,
             18.02277416}},
    /*13*/ {{0,           1,           2,           2,           2.321928095,
             2.321928095, 2.584962501, 2.584962501, 2.807354922, 3,
             3.321928095, 3.459431619, 3.807354922, 4.087462841, 4.459431619,
             4.857980995, 5.357552005, 5.882643049, 6.459431619, 7.129283017,
             7.851749041, 8.636624621, 9.46760555,  10.34207467, 11.2467406,
             12.17741954, 13.12702704, 14.09060867, 15.06444807, 16.04575966,
             17.0324655}},
    /*14*/ {{0,           1,           1.584962501, 2,           2,
             2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
             3,           3.321928095, 3.584962501, 3.807354922, 4.169925001,
             4.459431619, 4.906890596, 5.357552005, 5.882643049, 6.475733431,
             7.139551352, 7.857980995, 8.64385619,  9.47370575,  10.34429591,
             11.24911345, 12.1792871,  13.1283166,  14.09151803, 15.06507949,
             16.04622877}},
    /*15*/ {{0,           1,           1.584962501, 2,           2,
             2,           2.321928095, 2.321928095, 2.584962501, 2.807354922,
             2.807354922, 3.169925001, 3.321928095, 3.584962501, 3.807354922,
             4.169925001, 4.523561956, 4.906890596, 5.357552005, 5.906890596,
             6.491853096, 7.14974712,  7.87036472,  8.647458426, 9.477758266,
             10.34762137, 11.25148241, 12.18084157, 13.12944402, 14.09234422,
             15.06571064}},
    /*16*/ {{0,           1,           1.584962501, 1.584962501, 2,
             2,           2,           2.321928095, 2.321928095, 2.584962501,
             2.807354922, 3,           3.169925001, 3.321928095, 3.584962501,
             3.906890596, 4.169925001, 4.523561956, 4.906890596, 5.392317423,
             5.906890596, 6.491853096, 7.159871337, 7.876516947, 8.654636029,
             9.481799432, 10.35093918, 11.25384748, 12.18270471, 13.13073143,
             14.09325249}},
    /*17*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
             2,           2,           2,           2.321928095, 2.321928095,
             2.584962501, 2.807354922, 3,           3.169925001, 3.321928095,
             3.584962501, 3.906890596, 4.169925001, 4.523561956, 4.95419631,
             5.392317423, 5.930737338, 6.50779464,  7.159871337, 7.882643049,
             8.658211483, 9.485829309, 10.35424938, 11.25620869, 12.1842555,
             13.13185696}},
    /*18*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
             2,           2,           2,           2.321928095, 2.321928095,
             2.584962501, 2.584962501, 2.807354922, 3,           3.169925001,
             3.321928095, 3.584962501, 3.906890596, 4.169925001, 4.584962501,
             4.95419631,  5.426264755, 5.930737338, 6.523561956, 7.169925001,
             7.888743249, 8.665335917, 9.48984796,  10.357552,   11.25856603,
             12.18580462}},
    /*19*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
             1.584962501, 2,           2,           2,           2.321928095,
             2.321928095, 2.584962501, 2.584962501, 2.807354922, 3,
             3.169925001, 3.459431619, 3.700439718, 3.906890596, 4.247927513,
             4.584962501, 4.95419631,  5.426264755, 5.95419631,  6.523561956,
             7.17990909,  7.894817763, 8.668884984, 9.493855449, 10.35974956,
             11.26091953}},
    /*20*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
             1.584962501, 1.584962501, 2,           2,           2,
             2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
             3,           3.169925001, 3.459431619, 3.700439718, 3.906890596,
             4.247927513, 4.584962501, 5,           5.426264755, 5.95419631,
             6.539158811, 7.189824559, 7.900866808, 8.675957033, 9.497851837,
             10.36303963}},
    /*21*/ {{0,           1,           1,           1.584962501, 1.584962501,
             1.584962501, 1.584962501, 2,           2,           2,
             2,           2.321928095, 2.321928095, 2.584962501, 2.584962501,
             2.807354922, 3,           3.169925001, 3.459431619, 3.700439718,
             4,           4.247927513, 4.584962501, 5,           5.459431619,
             5.977279923, 6.554588852, 7.199672345, 7.906890596, 8.6794801,
             9.501837185}},
    /*22*/ {{0,           1,           1,           1.584962501, 1.584962501,
             1.584962501, 1.584962501, 1.584962501, 2,           2,
             2,           2.321928095, 2.321928095, 2.321928095, 2.584962501,
             2.807354922, 2.807354922, 3,           3.321928095, 3.459431619,
             3.700439718, 4,           4.247927513, 4.64385619,  5,
             5.459431619, 5.977279923, 6.554588852, 7.209453366, 7.912889336,
             8.682994584}},
    /*23*/ {{0,           1,           1,           1,           1.584962501,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 2,
             2,           2,           2.321928095, 2.321928095, 2.321928095,
             2.584962501, 2.807354922, 2.807354922, 3,           3.321928095,
             3.459431619, 3.700439718, 4,           4.321928095, 4.64385619,
             5.044394119, 5.491853096, 6,           6.569855608, 7.209453366,
             7.918863237}},
    /*24*/ {{0,           1,           1,           1,           1.584962501,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
             2,           2,           2,           2.321928095, 2.321928095,
             2.584962501, 2.584962501, 2.807354922, 3,           3.169925001,
             3.321928095, 3.459431619, 3.700439718, 4,           4.321928095,
             4.64385619,  5.044394119, 5.491853096, 6,           6.584962501,
             7.21916852}},
    /*25*/ {{0,           1,           1,           1,           1,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
             2,           2,           2,           2,           2.321928095,
             2.321928095, 2.584962501, 2.584962501, 2.807354922, 3,
             3.169925001, 3.321928095, 3.459431619, 3.807354922, 4,
             4.321928095, 4.64385619,  5.044394119, 5.491853096, 6.022367813,
             6.584962501}},
    /*26*/ {{0,           1,           1,           1,           1,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
             1.584962501, 2,           2,           2,           2,
             2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
             3,           3.169925001, 3.321928095, 3.584962501, 3.807354922,
             4,           4.321928095, 4.700439718, 5.087462841, 5.523561956,
             6.022367813}},
    /*27*/ {{0,           1,           1,           1,           1,
             1,           1.584962501, 1.584962501, 1.584962501, 1.584962501,
             1.584962501, 1.584962501, 2,           2,           2,
             2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501,
             2.807354922, 3,           3.169925001, 3.321928095, 3.584962501,
             3.807354922, 4.087462841, 4.392317423, 4.700439718, 5.087462841,
             5.523561956}},
    /*28*/ {{0,           1,           1,           1,           1,
             1,           1,           1.584962501, 1.584962501, 1.584962501,
             1.584962501, 1.584962501, 1.584962501, 2,           2,
             2,           2.321928095, 2.321928095, 2.321928095, 2.584962501,
             2.584962501, 2.807354922, 3,           3.169925001, 3.321928095,
             3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.700439718,
             5.087462841}},
    /*29*/ {{0,           1,           1,           1,           1,
             1,           1,           1.584962501, 1.584962501, 1.584962501,
             1.584962501, 1.584962501, 1.584962501, 2,           2,
             2,           2,           2.321928095, 2.321928095, 2.321928095,
             2.584962501, 2.807354922, 2.807354922, 3,           3.169925001,
             3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423,
             4.754887502}},
    /*30*/ {{0,           1,           1,           1,           1,
             1,           1,           1,           1.584962501, 1.584962501,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 2,
             2,           2,           2,           2.321928095, 2.321928095,
             2.584962501, 2.584962501, 2.807354922, 2.807354922, 3,
             3.169925001, 3.459431619, 3.584962501, 3.807354922, 4.087462841,
             4.392317423}},
    /*31*/ {{0,           1,           1,           1,           1,
             1,           1,           1,           1,           1.584962501,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
             2,           2,           2,           2,           2.321928095,
             2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922,
             3,           3.169925001, 3.459431619, 3.584962501, 3.906890596,
             4.087462841}},
    /*32*/ {{0,           1,           1,           1,           1,
             1,           1,           1,           1,           1.584962501,
             1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
             1.584962501, 2,           2,           2,           2.321928095,
             2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
             3,           3,           3.321928095, 3.459431619, 3.700439718,
             3.906890596}},
}};

std::vector<std::vector<double>> logbin_sizes_50bit{
    {/*0 */ {{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15,
              16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}},
     /*1 */ {{0,           1,           2,           3,           4,
              5,           5.977279923, 6.794415866, 7.622051819, 8.471675214,
              9.350939182, 10.25738784, 11.18673329, 12.13442632, 13.09638573,
              14.06886223, 15.04904021, 16.03484194, 17.02472847, 18.01752615,
              19.01241449, 20.00878969, 21.00622128, 22.00440154, 23.00311348,
              24.0022021,  25.00155732, 26.00110119, 27.00077858, 28.00055042,
              29.00038906}},
     /*2 */ {{0,           1,           2,           3,           4,
              4.95419631,  5.64385619,  6.321928095, 7.033423002, 7.787902559,
              8.588714636, 9.436711542, 10.31967212, 11.23122118, 12.16647695,
              13.11926538, 14.08514046, 15.0606115,  16.04307002, 17.03055938,
              18.02165778, 19.01534154, 20.01085997, 21.00768569, 22.00543781,
              23.00384642, 24.00272043, 25.0019238,  26.0013603,  27.00096173,
              28.00067986}},
     /*3 */ {{0,           1,           2,           3,           4,
              4.700439718, 5.247927513, 5.832890014, 6.459431619, 7.129283017,
              7.857980995, 8.64385619,  9.475733431, 10.34762137, 11.25207404,
              12.18146288, 13.12992693, 14.09275714, 15.06604713, 16.04691083,
              17.03328318, 18.02359194, 19.01671037, 20.01183055, 21.00837254,
              22.00592363, 23.00419011, 24.00296348, 25.00209568, 26.00148182,
              27.00104763}},
     /*4 */ {{0,           1,           2,           3,           3.906890596,
              4.459431619, 4.906890596, 5.392317423, 5.930737338, 6.523561956,
              7.17990909,  7.894817763, 8.672425342, 9.495855027, 10.36303963,
              11.26268214, 12.18920683, 13.13554898, 14.0967975,  15.06890421,
              16.04895509, 17.03474524, 18.02462568, 19.01744187, 20.01234901,
              21.00873909, 22.00618292, 23.00437376, 24.00309332, 25.00218746,
              26.00154671}},
     /*5 */ {{0,           1,           2,           3,           3.807354922,
              4.169925001, 4.584962501, 5,           5.459431619, 5.977279923,
              6.554588852, 7.209453366, 7.918863237, 8.686500527, 9.50779464,
              10.37177664, 11.26912668, 12.19383333, 13.13891172, 14.09918341,
              15.06149777, 16.05018877, 17.03560458, 18.02523691, 19.01787679,
              20.01265727, 21.0089572,  22.00633738, 23.00448281, 24.00317045,
              25.00224203}},
     /*6 */ {{0,           1,           2,           3,           3.584962501,
              3.906890596, 4.247927513, 4.64385619,  5.044394119, 5.491853096,
              6,           6.584962501, 7.22881869,  7.930737338, 8.696967526,
              9.515699838, 10.37721053, 11.2737956,  12.19690944, 13.1411492,
              14.10082657, 15.07175563, 16.05099646, 17.03618435, 18.02564786,
              19.01816757, 20.01286183, 21.00910213, 22.00644011, 23.0045555,
              24.00322193}},
     /*7 */ {{0,           1,           2,           3,           3.459431619,
              3.700439718, 4,           4.321928095, 4.700439718, 5.087462841,
              5.523561956, 6.022367813, 6.599912842, 7.238404739, 7.942514505,
              8.707359132, 9.52160044,  10.38154295, 11.27670602, 12.19936562,
              13.14290479, 14.10197567, 15.07263508, 16.05159132, 17.03661365,
              18.025956,   19.01838494, 20.01301592, 21.0092115,  22.0065175,
              23.00461019}},
     /*8 */ {{0,           1,           2,           3,           3.321928095,
              3.459431619, 3.807354922, 4.087462841, 4.392317423, 4.700439718,
              5.087462841, 5.523561956, 6.044394119, 6.614709844, 7.247927513,
              7.948367232, 8.710806434, 9.527477006, 10.3858624,  11.27961058,
              12.20120501, 13.14418024, 14.10295989, 15.07330478, 16.052101,
              17.03697846, 18.02621002, 19.01856696, 20.01314408, 21.00930241,
              22.00658153}},
     /*9 */ {{0,           1,           2,           2.807354922, 3.169925001,
              3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423,
              4.700439718, 5.129283017, 5.554588852, 6.044394119, 6.62935662,
              7.257387843, 7.960001932, 8.717676423, 9.531381461, 10.38801729,
              11.28193003, 12.20304206, 13.14545456, 14.10386149, 15.07397416,
              16.05254682, 17.03728955, 18.02643699, 19.01872722, 20.0132586,
              21.00938375}},
     /*10*/ {{0,           1,           2,           2.807354922, 3,
              3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841,
              4.392317423, 4.754887502, 5.129283017, 5.554588852, 6.06608919,
              6.62935662,  7.266786541, 7.965784285, 8.724513853, 9.535275377,
              10.39124359, 11.28366717, 12.20457114, 13.14656868, 14.10468065,
              15.07455962, 16.05297129, 17.03760057, 18.02665311, 19.01887933,
              20.0133663}},
     /*11*/ {{0,           1,           2,           2.584962501, 2.807354922,
              3,           3.169925001, 3.459431619, 3.584962501, 3.906890596,
              4.087462841, 4.392317423, 4.754887502, 5.129283017, 5.584962501,
              6.087462841, 6.64385619,  7.276124405, 7.971543554, 8.727920455,
              9.539158811, 10.39446269, 11.28598011, 12.20609861, 13.14768193,
              14.10549934, 15.07510305, 16.05339563, 17.03789009, 18.0268584,
              19.01902598}},
     /*12*/ {{0,           1,           2,           2.584962501, 2.807354922,
              2.807354922, 3,           3.169925001, 3.459431619, 3.700439718,
              3.906890596, 4.169925001, 4.459431619, 4.754887502, 5.169925001,
              5.584962501, 6.087462841, 6.64385619,  7.276124405, 7.977279923,
              8.731319031, 9.54303182,  10.39660478, 11.28771238, 12.20762447,
              13.14879432, 14.10623576, 15.07568805, 16.05377743, 17.03816882,
              18.02705826}},
     /*13*/ {{0,           1,           2,           2.321928095, 2.584962501,
              2.807354922, 3,           3.169925001, 3.321928095, 3.459431619,
              3.700439718, 3.906890596, 4.169925001, 4.459431619, 4.807354922,
              5.169925001, 5.614709844, 6.087462841, 6.658211483, 7.285402219,
              7.982993575, 8.73809226,  9.544964433, 10.39981196, 11.29001885,
              12.20884399, 13.14990586, 14.10705357, 15.07623105, 16.05418033,
              17.0384475}},
     /*14*/ {{0,           1,           2,           2.321928095, 2.584962501,
              2.584962501, 2.807354922, 3,           3.169925001, 3.321928095,
              3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.459431619,
              4.807354922, 5.169925001, 5.614709844, 6.108524457, 6.672425342,
              7.294620749, 7.988684687, 8.741466986, 9.548821908, 10.40194612,
              11.29174628, 12.21036695, 13.15085792, 14.1077892,  15.07677385,
              16.05456193}},
     /*15*/ {{0,           1,           2,           2.321928095, 2.321928095,
              2.584962501, 2.584962501, 2.807354922, 3,           3.169925001,
              3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.169925001,
              4.459431619, 4.807354922, 5.209453366, 5.614709844, 6.108524457,
              6.672425342, 7.303780748, 7.994353437, 8.744833837, 9.552669098,
              10.40514146, 11.29404631, 12.21188829, 13.15196787, 14.10852446,
              15.07731645}},
     /*16*/ {{0,           1,           2,           2.321928095, 2.321928095,
              2.321928095, 2.584962501, 2.807354922, 2.807354922, 3,
              3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596,
              4.169925001, 4.523561956, 4.807354922, 5.209453366, 5.64385619,
              6.129283017, 6.686500527, 7.312882955, 8,           8.751544059,
              9.556506055, 10.40726776, 11.29576893, 12.21340804, 13.15291858,
              14.10925934}},
     /*17*/ {{0,           1,           2,           2,           2.321928095,
              2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922,
              3,           3.169925001, 3.321928095, 3.584962501, 3.700439718,
              4,           4.247927513, 4.523561956, 4.857980995, 5.209453366,
              5.64385619,  6.129283017, 6.686500527, 7.312882955, 8.005624549,
              8.754887502, 9.560332834, 10.41045135, 11.2974895,  12.21462269,
              13.15402694}},
     /*18*/ {{0,           1,           2,           2,           2.321928095,
              2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
              2.807354922, 3,           3.169925001, 3.321928095, 3.584962501,
              3.700439718, 4,           4.247927513, 4.523561956, 4.857980995,
              5.209453366, 5.64385619,  6.14974712,  6.700439718, 7.321928095,
              8.011227255, 8.758223215, 9.562242424, 10.41256985, 11.2997804,
              12.21613956}},
     /*19*/ {{0,           1,           2,           2,           2,
              2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501,
              2.807354922, 2.807354922, 3,           3.169925001, 3.321928095,
              3.584962501, 3.807354922, 4,           4.247927513, 4.523561956,
              4.857980995, 5.247927513, 5.672425342, 6.14974712,  6.714245518,
              7.330916878, 8.016808288, 8.764871591, 9.566054038, 10.41468524,
              11.30149619}},
     /*20*/ {{0,           1,           1.584962501, 2,           2,
              2,           2.321928095, 2.321928095, 2.321928095, 2.584962501,
              2.584962501, 2.807354922, 3,           3,           3.169925001,
              3.321928095, 3.584962501, 3.807354922, 4,           4.247927513,
              4.523561956, 4.857980995, 5.247927513, 5.672425342, 6.169925001,
              6.714245518, 7.339850003, 8.022367813, 8.768184325, 9.569855608,
              10.41785251}},
     /*21*/ {{0,           1,           1.584962501, 2,           2,
              2,           2,           2.321928095, 2.321928095, 2.321928095,
              2.584962501, 2.584962501, 2.807354922, 3,           3,
              3.169925001, 3.459431619, 3.584962501, 3.807354922, 4,
              4.247927513, 4.584962501, 4.906890596, 5.247927513, 5.700439718,
              6.169925001, 6.727920455, 7.339850003, 8.027905997, 8.77148947,
              9.573647187}},
     /*22*/ {{0,           1,           1.584962501, 2,           2,
              2,           2,           2,           2.321928095, 2.321928095,
              2.584962501, 2.584962501, 2.584962501, 2.807354922, 3,
              3.169925001, 3.321928095, 3.459431619, 3.584962501, 3.807354922,
              4,           4.321928095, 4.584962501, 4.906890596, 5.285402219,
              5.700439718, 6.189824559, 6.727920455, 7.348728154, 8.033423002,
              8.77478706}},
     /*23*/ {{0,           1,           1.584962501, 1.584962501, 2,
              2,           2,           2,           2.321928095, 2.321928095,
              2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922,
              3,           3.169925001, 3.321928095, 3.459431619, 3.584962501,
              3.807354922, 4.087462841, 4.321928095, 4.584962501, 4.906890596,
              5.285402219, 5.700439718, 6.189824559, 6.741466986, 7.357552005,
              8.038918989}},
     /*24*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              2,           2,           2,           2,           2.321928095,
              2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
              2.807354922, 3,           3.169925001, 3.321928095, 3.459431619,
              3.584962501, 3.807354922, 4.087462841, 4.321928095, 4.584962501,
              4.906890596, 5.285402219, 5.727920455, 6.209453366, 6.741466986,
              7.357552005}},
     /*25*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              2,           2,           2,           2,           2,
              2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501,
              2.807354922, 2.807354922, 3,           3.169925001, 3.321928095,
              3.459431619, 3.700439718, 3.807354922, 4.087462841, 4.321928095,
              4.584962501, 4.95419631,  5.321928095, 5.727920455, 6.209453366,
              6.754887502}},
     /*26*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              1.584962501, 2,           2,           2,           2,
              2,           2.321928095, 2.321928095, 2.321928095, 2.584962501,
              2.584962501, 2.807354922, 2.807354922, 3,           3.169925001,
              3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.087462841,
              4.321928095, 4.64385619,  4.95419631,  5.321928095, 5.727920455,
              6.209453366}},
     /*27*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              1.584962501, 1.584962501, 2,           2,           2,
              2,           2.321928095, 2.321928095, 2.321928095, 2.321928095,
              2.584962501, 2.584962501, 2.807354922, 2.807354922, 3,
              3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596,
              4.087462841, 4.321928095, 4.64385619,  4.95419631,  5.321928095,
              5.754887502}},
     /*28*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              1.584962501, 1.584962501, 1.584962501, 2,           2,
              2,           2,           2.321928095, 2.321928095, 2.321928095,
              2.584962501, 2.584962501, 2.584962501, 2.807354922, 3,
              3,           3.169925001, 3.321928095, 3.459431619, 3.700439718,
              3.906890596, 4.087462841, 4.392317423, 4.64385619,  4.95419631,
              5.321928095}},
     /*29*/
     {{0,
       1,
       1.584962501,
       1.584962501,
       1.584962501,
       1.584962501,
       1.584962501,
       1.584962501,
       2,
       2,
       2,
       2,
       2,
       2.321928095,
       2.321928095,
       2.321928095,
       2.584962501,
       2.584962501,
       2.584962501,
       2.807354922,
       3,
       3,
       3.169925001,
       3.321928095,
       3.584962501,
       3.700439718,
       3.906890596,
       4.169925001,
       4.392317423,
       4.64385619,
       5}},
     /*30*/ {{0,           1,           1.584962501, 1.584962501, 1.584962501,
              1.584962501, 1.584962501, 1.584962501, 1.584962501, 2,
              2,           2,           2,           2,           2.321928095,
              2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922,
              2.807354922, 3,           3,           3.169925001, 3.321928095,
              3.584962501, 3.700439718, 3.906890596, 4.169925001, 4.392317423,
              4.700439718}},
     /*31*/ {{0,           1,           1,           1.584962501, 1.584962501,
              1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
              2,           2,           2,           2,           2,
              2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501,
              2.807354922, 2.807354922, 3,           3.169925001, 3.169925001,
              3.321928095, 3.584962501, 3.700439718, 3.906890596, 4.169925001,
              4.392317423}},
     /*32*/ {{0,           1,           1,           1.584962501, 1.584962501,
              1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501,
              1.584962501, 2,           2,           2,           2,
              2.321928095, 2.321928095, 2.321928095, 2.321928095, 2.584962501,
              2.584962501, 2.807354922, 2.807354922, 3,           3.169925001,
              3.321928095, 3.459431619, 3.584962501, 3.700439718, 3.906890596,
              4.169925001}}}};
std::vector<std::vector<double>> logbin_sizes_60bit{
    {/*0*/ {{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15, 16,
             17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}},
     /*1*/ {{0,       1,       2,       3,       4,       5,       5.97728,
             6.79442, 7.62205, 8.47168, 9.35094, 10.2574, 11.1867, 12.1344,
             13.0964, 14.0689, 15.049,  16.0348, 17.0247, 18.0175, 19.0124,
             20.0088, 21.0062, 22.0044, 23.0031, 24.0022, 25.0016, 26.0011,
             27.0008, 28.0006, 29.0004}},
     /*2*/ {{0,       1,       2,       3,       4,       4.9542,  5.64386,
             6.32193, 7.03342, 7.7879,  8.58871, 9.43671, 10.3197, 11.2312,
             12.1665, 13.1193, 14.0851, 15.0606, 16.0431, 17.0306, 18.0217,
             19.0153, 20.0109, 21.0077, 22.0054, 23.0038, 24.0027, 25.0019,
             26.0014, 27.001,  28.0007}},
     /*3*/ {{0,       1,       2,       3,       4,       4.70044, 5.24793,
             5.83289, 6.45943, 7.12928, 7.85798, 8.64386, 9.47573, 10.3476,
             11.2521, 12.1815, 13.1299, 14.0928, 15.066,  16.0469, 17.0333,
             18.0236, 19.0167, 20.0118, 21.0084, 22.0059, 23.0042, 24.003,
             25.0021, 26.0015, 27.001}},
     /*4*/ {{0,       1,       2,       3,       3.90689, 4.45943, 4.90689,
             5.39232, 5.93074, 6.52356, 7.17991, 7.89482, 8.67243, 9.49586,
             10.363,  11.2627, 12.1892, 13.1355, 14.0968, 15.0689, 16.049,
             17.0347, 18.0246, 19.0174, 20.0123, 21.0087, 22.0062, 23.0044,
             24.0031, 25.0022, 26.0015}},
     /*5*/ {{0,       1,       2,       3,       3.80735, 4.16993, 4.58496,
             5,       5.45943, 5.97728, 6.55459, 7.20945, 7.91886, 8.6865,
             9.50779, 10.3718, 11.2691, 12.1938, 13.1389, 14.0992, 15.0615,
             16.0502, 17.0356, 18.0252, 19.0179, 20.0127, 21.009,  22.0063,
             23.0045, 24.0032, 25.0022}},
     /*6*/ {{0,       1,       2,       3,       3.58496, 3.90689, 4.24793,
             4.64386, 5.04439, 5.49185, 6,       6.58496, 7.22882, 7.93074,
             8.69697, 9.5157,  10.3772, 11.2738, 12.1969, 13.1411, 14.1008,
             15.0718, 16.051,  17.0362, 18.0256, 19.0182, 20.0129, 21.0091,
             22.0064, 23.0046, 24.0032}},
     /*7*/ {{0,       1,       2,       3,       3.45943, 3.70044, 4,
             4.32193, 4.70044, 5.08746, 5.52356, 6.02237, 6.59991, 7.2384,
             7.94251, 8.70736, 9.5216,  10.3815, 11.2767, 12.1994, 13.1429,
             14.102,  15.0726, 16.0516, 17.0366, 18.026,  19.0184, 20.013,
             21.0092, 22.0065, 23.0046}},
     /*8*/ {{0,       1,       2,       3,       3.32193, 3.45943, 3.80735,
             4.08746, 4.39232, 4.70044, 5.08746, 5.52356, 6.04439, 6.61471,
             7.24793, 7.94837, 8.71081, 9.52748, 10.3859, 11.2796, 12.2012,
             13.1442, 14.103,  15.0733, 16.0521, 17.037,  18.0262, 19.0186,
             20.0131, 21.0093, 22.0066}},
     /*9*/ {{0,       1,       2,       2.80735, 3.16993, 3.32193, 3.58496,
             3.80735, 4.08746, 4.39232, 4.70044, 5.12928, 5.55459, 6.04439,
             6.62936, 7.25739, 7.96,    8.71768, 9.53138, 10.388,  11.2819,
             12.203,  13.1455, 14.1039, 15.074,  16.0525, 17.0373, 18.0264,
             19.0187, 20.0133, 21.0094}},
     /*10*/ {{0,       1,       2,       2.80735, 3,       3.16993, 3.32193,
              3.58496, 3.80735, 4.08746, 4.39232, 4.75489, 5.12928, 5.55459,
              6.06609, 6.62936, 7.26679, 7.96578, 8.72451, 9.53528, 10.3912,
              11.2837, 12.2046, 13.1466, 14.1047, 15.0746, 16.053,  17.0376,
              18.0267, 19.0189, 20.0134}},
     /*11*/ {{0,       1,       2,       2.58496, 2.80735, 3,       3.16993,
              3.45943, 3.58496, 3.90689, 4.08746, 4.39232, 4.75489, 5.12928,
              5.58496, 6.08746, 6.64386, 7.27612, 7.97154, 8.72792, 9.53916,
              10.3945, 11.286,  12.2061, 13.1477, 14.1055, 15.0751, 16.0534,
              17.0379, 18.0269, 19.019}},
     /*12*/ {{0,       1,       2,       2.58496, 2.80735, 2.80735, 3,
              3.16993, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943, 4.75489,
              5.16993, 5.58496, 6.08746, 6.64386, 7.27612, 7.97728, 8.73132,
              9.54303, 10.3966, 11.2877, 12.2076, 13.1488, 14.1062, 15.0757,
              16.0538, 17.0382, 18.0271}},
     /*13*/ {{0,       1,       2,       2.32193, 2.58496, 2.80735, 3,
              3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943,
              4.80735, 5.16993, 5.61471, 6.08746, 6.65821, 7.2854,  7.98299,
              8.73809, 9.54496, 10.3998, 11.29,   12.2088, 13.1499, 14.1071,
              15.0762, 16.0542, 17.0384}},
     /*14*/ {{0,       1,       2,       2.32193, 2.58496, 2.58496, 2.80735,
              3,       3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993,
              4.45943, 4.80735, 5.16993, 5.61471, 6.10852, 6.67243, 7.29462,
              7.98868, 8.74147, 9.54882, 10.4019, 11.2917, 12.2104, 13.1509,
              14.1078, 15.0768, 16.0546}},
     /*15*/ {{0,       1,       2,       2.32193, 2.32193, 2.58496, 2.58496,
              2.80735, 3,       3.16993, 3.32193, 3.45943, 3.70044, 3.90689,
              4.16993, 4.45943, 4.80735, 5.20945, 5.61471, 6.10852, 6.67243,
              7.30378, 7.99435, 8.74483, 9.55267, 10.4051, 11.294,  12.2119,
              13.152,  14.1085, 15.0773}},
     /*16*/ {{0,       1,       2,       2.32193, 2.32193, 2.32193, 2.58496,
              2.80735, 2.80735, 3,       3.16993, 3.32193, 3.45943, 3.70044,
              3.90689, 4.16993, 4.52356, 4.80735, 5.20945, 5.64386, 6.12928,
              6.6865,  7.31288, 8,       8.75154, 9.55651, 10.4073, 11.2958,
              12.2134, 13.1529, 14.1093}},
     /*17*/ {{0,       1,       2,       2,       2.32193, 2.32193, 2.58496,
              2.58496, 2.80735, 2.80735, 3,       3.16993, 3.32193, 3.58496,
              3.70044, 4,       4.24793, 4.52356, 4.85798, 5.20945, 5.64386,
              6.12928, 6.6865,  7.31288, 8.00562, 8.75489, 9.56033, 10.4105,
              11.2975, 12.2146, 13.154}},
     /*18*/ {{0,       1,       2,       2,       2.32193, 2.32193, 2.32193,
              2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993, 3.32193,
              3.58496, 3.70044, 4,       4.24793, 4.52356, 4.85798, 5.20945,
              5.64386, 6.14975, 6.70044, 7.32193, 8.01123, 8.75822, 9.56224,
              10.4126, 11.2998, 12.2161}},
     /*19*/ {{0,       1,       2,       2,       2,       2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993,
              3.32193, 3.58496, 3.80735, 4,       4.24793, 4.52356, 4.85798,
              5.24793, 5.67243, 6.14975, 6.71425, 7.33092, 8.01681, 8.76487,
              9.56605, 10.4147, 11.3015}},
     /*20*/ {{0,       1,       1.58496, 2,       2,       2,       2.32193,
              2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 3,       3,
              3.16993, 3.32193, 3.58496, 3.80735, 4,       4.24793, 4.52356,
              4.85798, 5.24793, 5.67243, 6.16993, 6.71425, 7.33985, 8.02237,
              8.76818, 9.56986, 10.4179}},
     /*21*/ {{0,       1,       1.58496, 2,       2,       2,       2,
              2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 3,
              3,       3.16993, 3.45943, 3.58496, 3.80735, 4,       4.24793,
              4.58496, 4.90689, 5.24793, 5.70044, 6.16993, 6.72792, 7.33985,
              8.02791, 8.77149, 9.57365}},
     /*22*/ {{0,       1,       1.58496, 2,       2,       2,       2,
              2,       2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735,
              3,       3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4,
              4.32193, 4.58496, 4.90689, 5.2854,  5.70044, 6.18982, 6.72792,
              7.34873, 8.03342, 8.77479}},
     /*23*/ {{0,       1,       1.58496, 1.58496, 2,       2,       2,
              2,       2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735,
              2.80735, 3,       3.16993, 3.32193, 3.45943, 3.58496, 3.80735,
              4.08746, 4.32193, 4.58496, 4.90689, 5.2854,  5.70044, 6.18982,
              6.74147, 7.35755, 8.03892}},
     /*24*/ {{0,       1,       1.58496, 1.58496, 1.58496, 2,       2,
              2,       2,       2.32193, 2.32193, 2.32193, 2.58496, 2.58496,
              2.80735, 2.80735, 3,       3.16993, 3.32193, 3.45943, 3.58496,
              3.80735, 4.08746, 4.32193, 4.58496, 4.90689, 5.2854,  5.72792,
              6.20945, 6.74147, 7.35755}},
     /*25*/ {{0,       1,       1.58496, 1.58496, 1.58496, 2,       2,
              2,       2,       2,       2.32193, 2.32193, 2.32193, 2.58496,
              2.58496, 2.80735, 2.80735, 3,       3.16993, 3.32193, 3.45943,
              3.70044, 3.80735, 4.08746, 4.32193, 4.58496, 4.9542,  5.32193,
              5.72792, 6.20945, 6.75489}},
     /*26*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 2,
              2,       2,       2,       2,       2.32193, 2.32193, 2.32193,
              2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993, 3.32193,
              3.45943, 3.70044, 3.90689, 4.08746, 4.32193, 4.64386, 4.9542,
              5.32193, 5.72792, 6.20945}},
     /*27*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 1.58496,
              2,       2,       2,       2,       2.32193, 2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993,
              3.32193, 3.45943, 3.70044, 3.90689, 4.08746, 4.32193, 4.64386,
              4.9542,  5.32193, 5.75489}},
     /*28*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 1.58496,
              1.58496, 2,       2,       2,       2,       2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 3,       3,
              3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.08746, 4.39232,
              4.64386, 4.9542,  5.32193}},
     /*29*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 1.58496,
              1.58496, 2,       2,       2,       2,       2,       2.32193,
              2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 3,
              3,       3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993,
              4.39232, 4.64386, 5}},
     /*30*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 1.58496,
              1.58496, 1.58496, 2,       2,       2,       2,       2,
              2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735,
              3,       3,       3.16993, 3.32193, 3.58496, 3.70044, 3.90689,
              4.16993, 4.39232, 4.70044}},
     /*31*/ {{0,       1,       1,       1.58496, 1.58496, 1.58496, 1.58496,
              1.58496, 1.58496, 1.58496, 2,       2,       2,       2,
              2,       2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735,
              2.80735, 3,       3.16993, 3.16993, 3.32193, 3.58496, 3.70044,
              3.90689, 4.16993, 4.39232}},
     /*32*/ {{0,       1,       1,       1.58496, 1.58496, 1.58496, 1.58496,
              1.58496, 1.58496, 1.58496, 1.58496, 2,       2,       2,
              2,       2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496,
              2.80735, 2.80735, 3,       3.16993, 3.32193, 3.45943, 3.58496,
              3.70044, 3.90689, 4.16993}}}};
std::vector<std::vector<double>> logbin_sizes_80bit{
    {/*0*/ {{0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15, 16,
             17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}},
     /*1*/ {{0,       1,       2,       3,       4,       5,       6,
             6.88264, 7.69349, 8.53138, 9.39874, 10.2946, 11.2143, 12.1551,
             13.1115, 14.0797, 15.0568, 16.0404, 17.0287, 18.0203, 19.0144,
             20.0102, 21.0072, 22.0051, 23.0036, 24.0026, 25.0018, 26.0013,
             27.0009, 28.0006, 29.0005}},
     /*2*/ {{0,       1,       2,       3,       4,       5,       5.78136,
             6.45943, 7.14975, 7.88264, 8.66888, 9.49785, 10.3652, 11.2656,
             12.1917, 13.1376, 14.0984, 15.0701, 16.0498, 17.0354, 18.0251,
             19.0178, 20.0126, 21.0089, 22.0063, 23.0045, 24.0032, 25.0022,
             26.0016, 27.0011, 28.0008}},
     /*3*/ {{0,       1,       2,       3,       4,       4.90689, 5.45943,
             6.02237, 6.61471, 7.25739, 7.96578, 8.72792, 9.5411,  10.3977,
             11.2889, 12.2085, 13.1496, 14.107,  15.0762, 16.0542, 17.0385,
             18.0273, 19.0193, 20.0137, 21.0097, 22.0069, 23.0048, 24.0034,
             25.0024, 26.0017, 27.0012}},
     /*4*/ {{0,       1,       2,       3,       4,       4.64386, 5.12928,
             5.58496, 6.10852, 6.6865,  7.31288, 8.00562, 8.75822, 9.56415,
             10.4136, 11.3009, 12.217,  13.1558, 14.1114, 15.0794, 16.0564,
             17.0401, 18.0284, 19.0201, 20.0143, 21.0101, 22.0071, 23.005,
             24.0036, 25.0025, 26.0018}},
     /*5*/ {{0,       1,       2,       3,       4,       4.45943, 4.80735,
             5.20945, 5.67243, 6.16993, 6.72792, 7.34873, 8.02791, 8.77479,
             9.57554, 10.4231, 11.3078, 12.2219, 13.1594, 14.1139, 15.0615,
             16.0577, 17.041,  18.0291, 19.0206, 20.0146, 21.0103, 22.0073,
             23.0052, 24.0037, 25.0026}},
     /*6*/ {{0,       1,       2,       3,       3.80735, 4.24793, 4.52356,
             4.90689, 5.2854,  5.70044, 6.18982, 6.74147, 7.36632, 8.04439,
             8.7879,  9.58496, 10.4284, 11.3117, 12.2252, 13.1616, 14.1155,
             15.0823, 16.0585, 17.0416, 18.0295, 19.0209, 20.0148, 21.0105,
             22.0074, 23.0052, 24.0037}},
     /*7*/ {{0,       1,       2,       3,       3.70044, 4,       4.32193,
             4.58496, 4.9542,  5.32193, 5.72792, 6.20945, 6.76818, 7.37504,
             8.05528, 8.79442, 9.59059, 10.4325, 11.3151, 12.2273, 13.1632,
             14.1167, 15.0831, 16.0591, 17.042,  18.0298, 19.0211, 20.0149,
             21.0106, 22.0075, 23.0053}},
     /*8*/ {{0,       1,       2,       3,       3.58496, 3.80735, 4.08746,
             4.32193, 4.64386, 4.9542,  5.32193, 5.75489, 6.22882, 6.76818,
             7.3837,  8.0607,  8.8009,  9.59432, 10.4357, 11.3174, 12.2291,
             13.1644, 14.1176, 15.0838, 16.0596, 17.0423, 18.03,   19.0213,
             20.0151, 21.0107, 22.0075}},
     /*9*/ {{0,       1,       2,       3,       3.45943, 3.70044, 3.90689,
             4.08746, 4.39232, 4.64386, 4.9542,  5.35755, 5.75489, 6.24793,
             6.78136, 7.39232, 8.06609, 8.80413, 9.59805, 10.4388, 11.3191,
             12.2306, 13.1655, 14.1184, 15.0844, 16.06,   17.0426, 18.0302,
             19.0214, 20.0152, 21.0107}},
     /*10*/ {{0,       1,       2,       3,       3.32193, 3.45943, 3.70044,
              3.90689, 4.16993, 4.39232, 4.64386, 5,       5.35755, 5.78136,
              6.24793, 6.79442, 7.40088, 8.07146, 8.80735, 9.60177, 10.4419,
              11.3214, 12.2321, 13.1666, 14.1191, 15.0849, 16.0604, 17.0429,
              18.0304, 19.0215, 20.0153}},
     /*11*/ {{0,       1,       2,       3,       3.16993, 3.32193, 3.58496,
              3.70044, 3.90689, 4.16993, 4.39232, 4.70044, 5,       5.35755,
              5.78136, 6.26679, 6.79442, 7.40088, 8.07682, 8.81378, 9.60363,
              10.444,  11.3231, 12.2333, 13.1676, 14.1198, 15.0854, 16.0607,
              17.0431, 18.0306, 19.0217}},
     /*12*/ {{0,       1,       2,       2.80735, 3,       3.16993, 3.32193,
              3.58496, 3.70044, 3.90689, 4.16993, 4.39232, 4.70044, 5,
              5.39232, 5.78136, 6.26679, 6.80735, 7.40939, 8.08215, 8.81698,
              9.60733, 10.446,  11.3247, 12.2345, 13.1685, 14.1205, 15.0859,
              16.0611, 17.0434, 18.0308}},
     /*13*/ {{0,       1,       2,       2.80735, 3,       3.16993, 3.32193,
              3.45943, 3.58496, 3.80735, 4,       4.16993, 4.45943, 4.70044,
              5.04439, 5.39232, 5.80735, 6.2854,  6.80735, 7.41785, 8.08746,
              8.82018, 9.61102, 10.4481, 11.3264, 12.236,  13.1695, 14.1211,
              15.0864, 16.0614, 17.0436}},
     /*14*/ {{0,       1,       2,       2.58496, 2.80735, 3,       3.16993,
              3.32193, 3.45943, 3.58496, 3.80735, 4,       4.16993, 4.45943,
              4.70044, 5.04439, 5.39232, 5.80735, 6.2854,  6.82018, 7.42626,
              8.09276, 8.82337, 9.61287, 10.4512, 11.3281, 12.2372, 13.1704,
              14.1219, 15.0868, 16.0618}},
     /*15*/ {{0,       1,       2,       2.58496, 2.80735, 2.80735, 3,
              3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4,       4.16993,
              4.45943, 4.75489, 5.04439, 5.42626, 5.83289, 6.2854,  6.83289,
              7.42626, 8.09803, 8.82972, 9.61655, 10.4533, 11.3298, 12.2384,
              13.1712, 14.1225, 15.0873}},
     /*16*/ {{0,       1,       2,       2.58496, 2.58496, 2.80735, 3,
              3,       3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4,
              4.24793, 4.45943, 4.75489, 5.04439, 5.42626, 5.83289, 6.30378,
              6.83289, 7.43463, 8.10329, 8.83289, 9.61839, 10.4553, 11.3315,
              12.2396, 13.1721, 14.1232}},
     /*17*/ {{0,       1,       2,       2.32193, 2.58496, 2.58496, 2.80735,
              3,       3,       3.16993, 3.32193, 3.45943, 3.58496, 3.80735,
              4,       4.24793, 4.45943, 4.75489, 5.08746, 5.42626, 5.83289,
              6.30378, 6.84549, 7.44294, 8.10852, 8.83605, 9.62205, 10.4574,
              11.3332, 12.2408, 13.1731}},
     /*18*/ {{0,       1,       2,       2.32193, 2.58496, 2.58496, 2.80735,
              2.80735, 3,       3,       3.16993, 3.32193, 3.45943, 3.70044,
              3.80735, 4,       4.24793, 4.45943, 4.75489, 5.08746, 5.42626,
              5.85798, 6.32193, 6.84549, 7.44294, 8.10852, 8.8392,  9.62571,
              10.4594, 11.3348, 12.242}},
     /*19*/ {{0,       1,       2,       2.32193, 2.32193, 2.58496, 2.58496,
              2.80735, 2.80735, 3,       3,       3.16993, 3.32193, 3.45943,
              3.70044, 3.80735, 4,       4.24793, 4.52356, 4.75489, 5.08746,
              5.45943, 5.85798, 6.32193, 6.85798, 7.45121, 8.11374, 8.84235,
              9.62753, 10.4625, 11.3365}},
     /*20*/ {{0,       1,       2,       2.32193, 2.32193, 2.32193, 2.58496,
              2.58496, 2.80735, 2.80735, 3,       3.16993, 3.16993, 3.32193,
              3.45943, 3.70044, 3.80735, 4.08746, 4.24793, 4.52356, 4.80735,
              5.08746, 5.45943, 5.85798, 6.33985, 6.85798, 7.45943, 8.11894,
              8.84549, 9.63118, 10.4645}},
     /*21*/ {{0,       1,       2,       2.32193, 2.32193, 2.32193, 2.58496,
              2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993, 3.16993,
              3.32193, 3.58496, 3.70044, 3.90689, 4.08746, 4.24793, 4.52356,
              4.80735, 5.12928, 5.45943, 5.88264, 6.33985, 6.87036, 7.45943,
              8.12412, 8.85175, 9.633}},
     /*22*/ {{0,       1,       2,       2,       2.32193, 2.32193, 2.32193,
              2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993,
              3.32193, 3.32193, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193,
              4.52356, 4.80735, 5.12928, 5.49185, 5.88264, 6.33985, 6.87036,
              7.46761, 8.12928, 8.85487}},
     /*23*/ {{0,       1,       2,       2,       2.32193, 2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3,
              3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.08746,
              4.32193, 4.52356, 4.80735, 5.12928, 5.49185, 5.88264, 6.35755,
              6.88264, 7.47573, 8.13443}},
     /*24*/ {{0,       1,       2,       2,       2,       2.32193, 2.32193,
              2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3,
              3,       3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689,
              4.08746, 4.32193, 4.58496, 4.80735, 5.12928, 5.49185, 5.90689,
              6.35755, 6.88264, 7.47573}},
     /*25*/ {{0,       1,       2,       2,       2,       2,       2.32193,
              2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735,
              3,       3,       3.16993, 3.32193, 3.45943, 3.58496, 3.70044,
              3.90689, 4.08746, 4.32193, 4.58496, 4.85798, 5.16993, 5.49185,
              5.90689, 6.37504, 6.89482}},
     /*26*/ {{0,       1,       2,       2,       2,       2,       2,
              2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735,
              2.80735, 3,       3,       3.16993, 3.32193, 3.45943, 3.58496,
              3.70044, 3.90689, 4.08746, 4.32193, 4.58496, 4.85798, 5.16993,
              5.52356, 5.90689, 6.37504}},
     /*27*/ {{0,       1,       1.58496, 2,       2,       2,       2,
              2,       2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496,
              2.80735, 2.80735, 3,       3,       3.16993, 3.32193, 3.45943,
              3.58496, 3.80735, 3.90689, 4.16993, 4.32193, 4.58496, 4.85798,
              5.16993, 5.52356, 5.93074}},
     /*28*/ {{0,       1,       1.58496, 2,       2,       2,       2,
              2,       2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496,
              2.58496, 2.80735, 2.80735, 3,       3,       3.16993, 3.32193,
              3.45943, 3.58496, 3.80735, 3.90689, 4.16993, 4.39232, 4.58496,
              4.85798, 5.16993, 5.52356}},
     /*29*/ {{0,       1,       1.58496, 1.58496, 2,       2,       2,
              2,       2,       2.32193, 2.32193, 2.32193, 2.32193, 2.58496,
              2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993, 3.16993,
              3.32193, 3.45943, 3.58496, 3.80735, 4,       4.16993, 4.39232,
              4.58496, 4.85798, 5.16993}},
     /*30*/ {{0,       1,       1.58496, 1.58496, 2,       2,       2,
              2,       2,       2,       2.32193, 2.32193, 2.32193, 2.32193,
              2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3,       3.16993,
              3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4,       4.16993,
              4.39232, 4.64386, 4.90689}},
     /*31*/ {{0,       1,       1.58496, 1.58496, 1.58496, 2,       2,
              2,       2,       2,       2,       2.32193, 2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 2.80735, 3,
              3.16993, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4,
              4.16993, 4.39232, 4.64386}},
     /*32*/ {{0,       1,       1.58496, 1.58496, 1.58496, 1.58496, 2,
              2,       2,       2,       2,       2.32193, 2.32193, 2.32193,
              2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3,
              3,       3.16993, 3.32193, 3.32193, 3.45943, 3.70044, 3.80735,
              4,       4.16993, 4.39232}}}};

}  // namespace

uint64_t SimpleIndex::GetBinSize(uint64_t num_bins, uint64_t num_balls,
                                 uint64_t stat_sec_param, bool approx) {
  SPDLOG_DEBUG("num_bins:{}, num_balls:{}, approx:{}", num_bins, num_balls,
               approx);

  if (num_bins < 2) {
    return num_balls;
  }

  if (approx) {
    auto& sizes = [&]() -> std::vector<std::vector<double>>& {
      if (stat_sec_param <= 40) {
        return logbin_sizes_40bit;
      }
      if (stat_sec_param <= 50) {
        return logbin_sizes_50bit;
      }
      if (stat_sec_param <= 60) {
        return logbin_sizes_60bit;
      }
      return logbin_sizes_80bit;
    }();

    auto num_bins_low = std::floor(std::log2(num_bins));
    auto num_bins_hgh = std::ceil(std::log2(num_bins));
    auto num_balls_low = std::floor(std::log2(num_balls));
    auto num_balls_hgh = std::ceil(std::log2(num_balls));

    auto diff_bin = std::log2(num_bins) - num_bins_low;
    auto diff_ball = std::log2(num_balls) - num_balls_low;

    SPDLOG_DEBUG(
        "num_bins_low:{}, num_bins_hgh:{}, num_balls_low:{}, num_balls_hgh:{}",
        num_bins_low, num_bins_hgh, num_balls_low, num_balls_hgh);
    SPDLOG_DEBUG("diff_bin:{}, diff_ball:{}", diff_bin, diff_ball);

    // interpolate a linear 2d spline between the serounding points (a surface).
    // Then evalate the surface at out bin,ball coordinate.
    if (num_bins_hgh < sizes.size() &&
        num_balls_hgh < sizes[num_bins_hgh].size()) {
      auto a0 = (diff_bin)*sizes[num_bins_low][num_balls_low] +
                (1 - diff_bin) * sizes[num_bins_low][num_balls_hgh];
      auto a1 = (diff_bin)*sizes[num_bins_hgh][num_balls_low] +
                (1 - diff_bin) * sizes[num_bins_hgh][num_balls_hgh];

      auto b0 = (diff_ball)*a0 + (1 - diff_ball) * a1;

      auto B = std::ceil(std::pow(2, b0));

#if !defined(NDEBUG) && defined(ENABLE_BOOST)
      auto B2 = get_bin_size(numBins, numBalls, statSecParam, false);
      YACL_ENFORCE(B2 <= B);
#endif

      return B;
    }
  }

  auto B = std::max<uint64_t>(1, num_balls / num_bins);
  double current_prob = GetBinOverflowProb(num_bins, num_balls, B);
  uint64_t step = 1;

  bool doubling = true;

  while (current_prob < stat_sec_param || step > 1) {
    YACL_ENFORCE(step, "setp:{} current_prob:{}", step, current_prob);

    if (stat_sec_param > current_prob) {
      if (doubling) {
        step = std::max<uint64_t>(1, step * 2);
      } else {
        step = std::max<uint64_t>(1, step / 2);
      }

      B += step;
    } else {
      doubling = false;
      step = std::max<uint64_t>(1, step / 2);
      B -= step;
    }
    current_prob = GetBinOverflowProb(num_bins, num_balls, B);
  }

  return B;
}

}  // namespace psi::rr22::okvs
